(* Copyright (C) 2010 School of Software Engineering, 
 * University of Science and Technology of China.
 *
 * This code is released under a BSD-style license.
 * See the file LICENSE for details.
 *)

functor Dict (S: DICT_STRUCTS):> DICT =
struct

open S

datatype ('a, 'b) t = T of {compare: 'a * 'a -> order,
                            table: ('a * 'b) list}
                        
exception Notfound

fun new {compare = f} = T {compare = f,
                           table = []}
    
fun enter (T {compare = f, table = t}, k, v) = 
    T {compare = f,
       table = (k, v)::t}

fun layout (T {compare, table}, laya, layb) =
    Layout.seq (List.map 
                    (fn (a, b) =>
                        Layout.seq [laya a, Layout.str ": ", layb b, 
                                    Layout.str ", "])
                    table)
    
fun lookup (T {compare, table}, k) =
    let val rec loop =
         fn [] => raise Notfound
          | (x, v)::xs =>
            (case compare (k, x)
              of EQUAL => v
               | _ => loop xs)
    in  loop table
    end

end
